Generally, the compilation of a software application program may be performed in two steps: the first step before distribution and the second step after distribution, such as at the time of execution. This two-part compilation allows the software application to be distributed as bytecode (e.g., Dalvik bytecode) so that an optimizer may optimize the code for the specific machine on which the code is to be executed. As an example, Dalvik is a process virtual machine (VM) on the Google™ Android operating system that converts Dalvik bytecode to ARM executable object code prior to execution. This system allows the software applications to be easily ported to any computing device having virtualization software (e.g., Dalvik) that supports the instruction set architecture used by the first compiler, regardless of the device's underlying hardware and operating system interface.
Currently, an off-line compiler may parse an entire software application program and generate an intermediate representation (IR) to represent the program structure. This IR typically carries extra information, such as annotations on the abstract syntax tree, which may be used at code generation time by a dynamic or just-in-time (JIT) compiler to analyze and optimize the program, such as by determining the parts of the program that will not be executed in the current environment and removing such code (i.e., identifying code that will never be executed because it is not reachable on any path from start to end of the program in the current implementation or activation circumstance).
In dynamic languages, such as JavaScript, the parsing and compilation occurs at run-time, just before program execution. Parsing is the process of analyzing a text to determine its grammatical structure with respect to a given formal grammar, and in the interpretation of programs, parsing includes reading in the source script and converting it into an intermediate representation based on the language semantics of the program language. For most dynamic and/or scripting languages, parsing generates a bytecode representation of the program that is fed into an interpreter, which may invoke a just-in-time compiler to generate machine code for selected portions of the code.
Thus, for both static and dynamic languages, a just-in-time (JIT) compiler may analyze and optimize the program to generate more-performant binary or machine code. Since such optimizations are performed at runtime, the compilation processing time becomes part of the overall program execution time.
Modern JIT compilers may implement any of a number of machine-independent, global compiler optimizations to generate the more-performant binary code. Such optimizations include Dead Code Elimination (DCE), Sparse Conditional Constant Propagation (SCCP), Algebraic Simplification (AS), and Global Value Numbering (GVN), each of which may be classified as being either a “forwards pass” optimization or a “backwards pass” optimization.
Many JIT compilers implement each of these optimizations as individual passes over the Internal Representation (IR) of the input program. Another approach is to combine these optimizations into a single framework and have an iterative (i.e., multiple forwards followed by backwards passes or vice versa) fixed-point solution.
However, current solutions are not suitable for use in constrained computing environments, such as in mobile devices, which have limited processing and/or battery resources. Iterative point solutions may also take so long to complete that the user's experience is adversely affected when the user attempts to launch an application. For example, while the iterative solution has been shown to produce highly optimized code, the iterative solution suffers from the drawback of potentially taking a large number of iterations over the IR. As such, this solution is not very appropriate for a JIT compiler in the mobile domain where speed of compilation (and responsiveness to an application) is very important.